package io.github.hadyang.leetcode.algo;

import java.util.Arrays;

/** @author haoyang.shi */
public class QSort {

  public void sort(int[] arr, int low, int high) {
    int l = low;
    int h = high;
    int povit = arr[low];

    while (l < h) {
      while (l < h && arr[h] >= povit) h--;
      if (l < h) {
        arr[l] = arr[h];
        l++;
      }

      while (l < h && arr[l] <= povit) l++;

      if (l < h) {
        arr[h] = arr[l];
        h--;
      }
    }

    arr[l] = povit;

    System.out.print("l=" + (l + 1) + ";h=" + (h + 1) + ";povit=" + povit + "\n");
    System.out.println(Arrays.toString(arr));
    if (l - 1 > low) sort(arr, low, l - 1);
    if (h + 1 < high) sort(arr, h + 1, high);
  }

  public static void main(String[] args) {
    QSort qSort = new QSort();
    int[] ints = {10, 9, 11, 23, 5, 7};
    qSort.sort(ints, 0, ints.length - 1);

    System.out.println(Arrays.toString(ints));
  }
}
